package com.lw.leetcode.arr.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2397. 被列覆盖的最多行数
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/5 14:10
 */
public class MaximumRows {


    public static void main(String[] args) {
        MaximumRows test = new MaximumRows();
        int[][] arr = {{0, 0, 0}, {1, 0, 1}, {0, 1, 1}, {0, 0, 1}};
        int k = 2;

        int i = test.maximumRows(arr, k);
        System.out.println(i);
    }

    public int maximumRows(int[][] mat, int cols) {
        int m = mat.length;
        int n = mat[0].length;
        int max = 0;
        int st = (1 << cols) - 1;
        int end = (1 << n) - (1 << (n - cols));
        int[] arr = new int[m];
        for (int i = st; i <= end; i++) {
            if (Integer.bitCount(i) != cols) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                if ((i | (1 << j)) == i) {
                    continue;
                }
                for (int k = 0; k < m; k++) {
                    if (mat[k][j] == 1) {
                        arr[k] = 1;
                    }
                }
            }
            int c = 0;
            for (int j = 0; j < m; j++) {
                c += arr[j];
            }
            Arrays.fill(arr, 0);
            max = Math.max(max, m - c);
        }
        return max;
    }

}
